package vip.zhenzicheng.algorithm.leetcode.stack_queue;

/**
 * <a href="https://leetcode.cn/problems/largest-rectangle-in-histogram/">柱状图中最大的矩形 [困难]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-24 10:55
 */
public class LargestRectangleInHistogram_84 {

  /*单调栈+哨兵*/
  // public int largestRectangleArea(int[] heights) {
  //   if (heights.length == 0) {
  //     return 0;
  //   }
  //   if (heights.length == 1) {
  //     return heights[0];
  //   }
  //   int area = 0;
  //   int[] sentinelHeights = new int[heights.length + 2]; // 存放头尾哨兵
  //   sentinelHeights[0] = 0; // 头哨兵，它不会大于任何输入元素，即不会出栈，栈不为空
  //   System.arraycopy(heights, 0, sentinelHeights, 1, heights.length); // 将原始数组拷贝到新数组，并跳过头哨兵
  //   sentinelHeights[heights.length + 1] = 0; // 尾哨兵
  //   int sentinelLen = sentinelHeights.length; // 新数组长度 = old + 2
  //
  //   Deque<Integer> stack = new LinkedList<>(); // 模拟单调栈（栈顶最大，栈底最小）
  //   stack.push(0); // 头哨兵入栈
  //
  //   for (int i = 1; i < sentinelLen; i++) {
  //     while (sentinelHeights[i] < sentinelHeights[stack.peek()]) { // 只要放不进代表之前有更大的，一直出栈算面积
  //       int curHeight = sentinelHeights[stack.pop()];
  //       int curWidth = i - stack.peek() - 1;
  //       area = Math.max(area, curHeight * curWidth); // 保存一个最大面积
  //     }
  //     stack.push(i);
  //   }
  //   return area;
  // }

  /*双向寻找，利用之前的计算结果加速*/
  public int largestRectangleArea(int[] heights) {
    int[] leftLower = new int[heights.length];
    int[] rightLower = new int[heights.length];
    // 初始化，最左和最右都在边界外
    rightLower[heights.length - 1] = heights.length;
    leftLower[0] = -1;

    // 正序遍历
    for (int i = 1; i < heights.length; i++) {
      // 从当前元素左侧第一个邻居开始往左侧寻找
      int prevLeft = i - 1;
      // 不断寻找直到数组头或者找到第一个小于当前元素的邻居元素
      while (prevLeft >= 0 && heights[prevLeft] >= heights[i]) {
        // 在遍历的过程中，当前元素的左侧元素已经处理过，所以利用之前的结果数组可以跳跃加速
        prevLeft = leftLower[prevLeft];
      }
      leftLower[i] = prevLeft;
    }

    // 逆序遍历，对当前元素向右找
    for (int i = heights.length - 2; i >= 0; i--) {
      int nextRight = i + 1;
      while (nextRight < heights.length && heights[nextRight] >= heights[i]) {
        nextRight = rightLower[nextRight];
      }
      rightLower[i] = nextRight;
    }

    // 找得到所有元素的对应邻居元素，寻找最大
    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
      maxArea = Math.max(maxArea, heights[i] * (rightLower[i] - leftLower[i] - 1));
    }
    return maxArea;
  }
}
